The X-linked inhibitor of apoptosis (XIAP) is a promising new molecular target for the design of novel anticancer drugs aiming at overcoming apoptosis-resistance of cancer cells to chemotherapeutic agents and radiation therapy. Recent studies demonstrated that the BIR3 domain of XIAP where caspase-9 and Smac proteins bind is an attractive site for designing small-molecule inhibitors of XIAP. Through computational structure-based screening of an in-house traditional herbal medicine three-dimensional structure database of 8221 individual natural products, followed by biochemical testing of selected candidate compounds, we discovered embelin from the Japanese Ardisia herb as a small-molecular weight inhibitor that binds to the XIAP BIR3 domain. We showed that embelin binds to the XIAP BIR3 protein with an affinity similar to that of the natural Smac peptide using a fluorescence polarization-based binding assay. Our NMR analysis further conclusively confirmed that embelin interacts with several crucial residues in the XIAP BIR3 domain with which Smac and caspsase-9 bind. Embelin inhibits cell growth, induces apoptosis, and activates caspase-9 in prostate cancer cells with high levels of XIAP, but has a minimal effect on normal prostate epithelial and fibroblast cells with low levels of XIAP. In stably XIAP-transfected Jurkat cells, embelin effectively overcomes the protective effect of XIAP to apoptosis and enhances the etoposide-induced apoptosis and has a minimal effect in Jurkat cells transfected with vector control. Taken together, our results showed that embelin is a fairly potent, nonpeptidic, cell-permeable, small-molecule inhibitor of XIAP and represents a promising lead compound for designing an entirely new class of anticancer agents that target the BIR3 domain of XIAP.